Show how to phrase the TSP approximation using an MST as a minimum-cost, perfect matching problem, followed by a simple Eulerian path (a path that crosses every edge of its given graph, something that always exists in a connected graph in which every vertex has even degree).

Note: this is called Christofides' algorithm, after its author, who first published it in 1976. You
can of course trivially find this on Wikipedia, but the idea is to work it out on your own. Hint:
shortcuts must go from one vertex of odd degree to another vertex of odd degree.

\vspace{10pt}

In this question we need to find an approximate solution of the TSP problem (travelling salesman problem):  Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.

We'll consider metric TSP problem where the triangle inequation holds: $\forall x,y,z \quad d(x,y) \le d(x,z) + d(z,y)$ where $x$,$y$ and $z$ are cities and $d(x,y)$ is the distance between two cities. This inequation will give us a possibility to replace two adjacent edges by the shortcut. 

Suppose we have found an MST on the input fully connected graph. We know that going round of MST (minimum spanning tree) gives us the first approximation of TSP solution with approximation ratio 2\footnote{This case was discussed on the lecture}. So we need to somehow improve this cycle. To do so we need to add shortcuts between some nodes in MST and use them instead of edges of MST.

We know from the hint that shortcuts must go from one vertex of odd degree to another vertex of odd degree and the graph with all vertices of even degree has the advantage of having Eulerian path in it. So we want to add the shortcuts between vertices of odd degree in a way that all vertices of odd degree will have even degree in the end. But we don't want to add a lot of edges, as it increases the cost of found Eulerian path. So we want to add exactly one new edge to each such vertex, what means that we want to find a perfect matching between them. As we aim to diminish the cost of result Eulerian path the cost of this matching should be minimized.

Here we should note that it is possible to construct the perfect matching over all the vertices with odd degree, because the number of such vertices in even: the sum of degrees of all vertices is even, because it equals twice the number of edges (each edge is used in two vertex degrees). If we subtract even sum of all even degrees from the sum of all degrees, we'll get the sum of all odd degrees that also has to be even. Thus, the number of vertices with odd degree is even.

So after adding the edges of found perfect matching between all vertices of odd degree, they all will have even degree. In result every vertex in constructed graph has even degree and we can find an Eulerian path that traverse all edges and thus all vertices of the graph, as it is connected.

This Eulerian path is already an improvement over the initial approximation of cycle around MST, but it requires refinement, as it can go through some vertices twice. Using the same idea with shortcuts for this found path, we'll change some adjacent edges in the path by shortcut, so that all vertices still remain traversed, but only once.

\newpage

The algorithm based on described ideas was developed by Christofides in 1976. It has the following steps:

\begin{enumerate}

\item Find an MST $T$ in the fully connected graph $G=(V,E)$, where $V$ is the given set of cities, and each edge in $E$ has cost equalling to the distance between cities
\item Define $V_{odd} \subseteq V$ as the subset of vertices that have odd degree in constructed MST $T$ 
\item Find the minimum-cost perfect matching $M$ of $V_odd$ given the edges from $E$ between all vertices of $V_{odd}$
\item Find Eulerian path $P$ in the graph $G^{\prime} = T \cup M$, what means that $G^{\prime}$ includes all vertices $V$ and all edges from $T$ and $M$
\item While path $P$ doesn't meet the requirement of TSP (is not Hamiltonian), traverse $P$ and replace adjacent edges intersecting in a vertex with degree higher than 2 by a shortcut 



\end{enumerate}

